This invention relates generally to interactive data editing, and more particularly to the undoing of editing operations performed on a data object.
There are many interactive data-editing software applications developed for interactively editing a wide variety of data objects, such as text documents, business charts, engineering drawings, digital pictures and computer graphics, etc. With commonly used interactive data-editing applications, a user modifies a data object by interactively applying consecutive editing operations to the data object. For example, the user of a word processing program edits a text document by typing and deleting words, cutting, pasting, reformatting, etc., and the user of a digital painting program may modify a picture by applying multiple strokes of various digital paintbrushes. Regardless of the types of data object and interactive editing operations involved, the user would from time to time decide that the effects of the last one or few editing steps are not desirable and would want to remove the changes made by those editing steps. To that end, most interactive data-editing applications available nowadays support an xe2x80x9cundoxe2x80x9d function that restores the data object being edited back to its state right before the last editing steps were performed.
A widely used approach to implement the undo function may be termed the xe2x80x9cbackward-uncreatexe2x80x9d approach. Under this approach, to undo the last editing step, the inverse of the last editing command is applied to the data object to return it to its previous state. This backward-uncreate approach is commonly used in word processing programs to undo editing operations. To enable the undoing of editing operations, the editing commands (e.g., insertion, deletion, cutting, pasting, formatting, etc.) and the corresponding changes (such as the inserted or deleted portions) may be saved in a buffer. Each time the user selects the undo function, the inverse of the last editing operation is applied to the document to recreate its prior state. By way of example, a deletion performed on a document can be undone by reinserting the deleted portion into the document. By selecting the undo function multiple times, the user can undo multiple consecutive editing steps applied to a document.
This backward-uncreate approach, however, cannot be universally used with all types of interactive editing operations. This is because some editing operations are non-invertable, i.e., the prior state cannot be recovered by applying an xe2x80x9cinversexe2x80x9d of the editing operation to be undone. An example of such non-invertable editing operation is the application of a digital painting stroke to a digital picture. A digital picture contains a plurality of pixels each having color data defining the color of that pixel. If a digital brush stroke with an opaque color is applied to the picture, the original color data of those pixels of the picture touched by the brush are overwritten by the new color data. The original color data cannot later be recreated from the new color data even though the effects of the brush stroke are known. As a result, the undoing of a digital painting stroke cannot be implemented using the backward-uncreate approach.
The non-invertability of the painting strokes makes it more difficult to implement a satisfactory undo mechanism. Currently, it has been proposed to allow the last painting stroke to be undone quickly by saving the state of the picture right before the last stroke in the memory. When the user elects to undo the last stroke, the picture is simply restored to the saved prior state. Although this mechanism is relatively fast, it can handle only the undoing of the last painting stroke. If the user wants to undo the second last stroke, the picture has to be regenerated stroke by stroke from the very first stroke of the painting session up to the third last stroke. If the third last stroke is then to be undone, the picture will be regenerated again by applying all strokes from the first stroke up to the fourth last stroke. As a result, the multiple-undo operation, i.e., the operation of undoing more than the last editing operation, can be unacceptably slow when the number of existing strokes in the picture is large.
One possible way to improve the speed of the multiple-undo operation is to store the prior states of the picture for the most recent several strokes. A multiple-undo operation can be quickly performed as long as the state to which the picture is to be restored has been stored in the memory. This approach is, however, generally unfavorable. First of all, the depth of this undo mechanism, i.e., the number of consecutive strokes that can efficiently undone, is still limited by the number of the most recent prior states stored in the memory. Moreover, the amount of memory required to store the most recent prior states of the picture can be very large even for a very modest depth of operation.
There is therefore a need for an undo mechanism that can be used to undo multiple non-invertable editing operations, such as digital painting strokes applied by a user of a digital painting program, that is reasonably fast, has a reasonable large depth of operation, and does not impose an unacceptably high demand of memory space.
In accordance with the invention, there is provided a method and system for undoing multiple editing operations on a data object that provides improved performance in terms of speed, operation depth, and memory required, and can be used in undoing non-invertable editing operations. In the course of the editing process, a plurality of prior states are stored in the memory. The stored prior states correspond to previously performed editing operations that are spaced at uneven and preferably generally exponentially increasing intervals. When an undesired editing operation is to be undone, the data object is first restored to a stored prior state. If that restored state is not the target state (i.e., the state immediately prior to the undesired editing operation), all previously performed editing operations between the restored state and the undesired operation are reapplied to the data object to recreate the target state.
Other advantages will become apparent with reference to the following detailed description when taken in conjunction with the drawings in which: